package com.cheng.learn.leetcode;

import java.util.*;

/**
 * @description: 常数时间插入、删除和获取随机元素
 * @author: ChengHaiZhu
 * @create: 2021-03-21 23:04
 **/
public class RandomizedSet380 {

    // 存储值和索引的对应关系
    Map<Integer, Integer> dict;
    // 存储值
    List<Integer> list;
    // 获取随机值
    Random rand = new Random();
    /**
     * 无参构造方法
     */
    public RandomizedSet380() {
        dict = new HashMap();
        list = new ArrayList();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (dict.containsKey(val))
            return false;
        dict.put(val, list.size());
        list.add(list.size(), val);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (! dict.containsKey(val)) return false;

        // move the last element to the place idx of the element to delete
        int lastElement = list.get(list.size() - 1);
        int idx = dict.get(val);
        list.set(idx, lastElement);
        dict.put(lastElement, idx);
        // delete the last element
        list.remove(list.size() - 1);
        dict.remove(val);
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}
